package com.dycong.common.leetcode.yi;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-09-09
 * Time: 17:27
 */
public class TopKFrequent {
    public static void main(String[] args) {
        topKFrequent(new int[]{1, 1, 1, 2, 2, 3, 5, 5, 5, 5, 5, 3, 3, 3, 3}, 3).stream().forEach(item -> System.out.println(item));
    }

    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> masp = new HashMap<>();
        for (Integer item : nums) {
            masp.put(item, masp.getOrDefault(item, 0) + 1);
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((n1, n2) -> masp.get(n1) - masp.get(n2));

        for (Integer item : masp.keySet()) {
            priorityQueue.add(item);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        List<Integer> result = new ArrayList<>(priorityQueue.size());
        while (k-- > 0) {
            result.add(priorityQueue.poll());
        }
        return result;
    }
}
